package leetcode.editor.cn.dsa24_dijkstra;
//给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b
//的一条无向边，且该边遍历成功的概率为 succProb[i] 。 
//
// 指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。 
//
// 如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。 
//
// 示例 1： 
// 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, e
//nd = 2
//输出：0.25000
//解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
// 
// 示例 2：
// 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, e
//nd = 2
//输出：0.30000
//
// 示例 3： 
// 输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
//输出：0.00000
//解释：节点 0 和 节点 2 之间不存在路径
//
// 提示： 
// 2 <= n <= 10^4
// 0 <= start, end < n 
// start != end 
// 0 <= a, b < n 
// a != b 
// 0 <= succProb.length == edges.length <= 2*10^4 
// 0 <= succProb[i] <= 1 
// 每两个节点之间最多有一条边 
// 
// Related Topics 图 
// 👍 42 👎 0

import java.util.ArrayList;
import java.util.PriorityQueue;

public class PathWithMaximumProbability1514 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
            // 构建有权图的邻接表
            ArrayList<ArrayList<int[]>> adj = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 0; i < edges.length; i++) {
                // int[]存储的是边的邻居节点, 权重的索引位置
                // 由于是无向边，所以一条边需要存储两条记录，例如a[b,0.5]和b[a,0.5]
                adj.get(edges[i][0]).add(new int[]{edges[i][1], i});
                adj.get(edges[i][1]).add(new int[]{edges[i][0], i});
            }
            // 存储从源节点src成功到各个节点的最大概率
            int[] dist = new int[n];
            // 优先队列(大顶堆)，根据概率大小排序
            PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
                return o2[1] - o1[1];
            });
            // 由于允许的误差不超过 1e-5，因此需要记录6位小数值，我们将其转为整数计算
            queue.offer(new int[]{start, 1000000});
            while (!queue.isEmpty()) {
                int[] poll = queue.poll();
                int vert = poll[0], prob = poll[1];
                if (vert == end) return prob/1000000.0;
                for(int[] info : adj.get(vert)) {
                    int newDis = (int)(prob * succProb[info[1]]);
                    // 虽然有记录双向边，存在环的情况，但是由于双向边是有权重的
                    // 当遍历a->b时，记录权重0.5，如果从b返回a，权重为0.25，因此不可能走回头路
                    // 所以求单条路径最短情况一般不用考虑记录已访问过的节点
                    if (newDis > dist[info[0]]) { // 概率更大则更新概率值同时入队
                        dist[info[0]] = newDis;
                        queue.offer(new int[]{info[0], newDis});
                    }
                }
            }
            return 0;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}